package leetcode.D200.T124;

import util.TreeNode;

class Solution {
    private int maxPath = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        int max = getMaxPath(root);
        return Math.max(max, maxPath);
    }

    /**
     * 这里返回的是路径一定是有一个端点是root
     * 对于不满足这种条件的路径，也有可能是是最长的路径，所以交给maxPath去检验
     * 不过有个特例，就是当root为null时，返回的是0，要单独处理
     */
    private int getMaxPath(TreeNode root) {
        if (root == null)
            return 0;
        if (root.left == null && root.right == null) {
            maxPath = Math.max(maxPath, root.val);
            return root.val;
        }
        int left = getMaxPath(root.left), right = getMaxPath(root.right);
        /**
         * 对于所有不满足「有一个端点是root」条件的路径，需要用maxPath进行过滤，以免漏过
         *      其中不包含root.left或root.right的路径已经在递归中被maxPath检验过，这里无需检验
         *      剩下的分三种：
         *          以root.left为端点的
         *          以root.right未端点的
         *          跨root的
         * 必须排除「空路径」
         */
        if (root.left == null || root.right == null)
            maxPath = Math.max(maxPath, Math.max(left + right + root.val, root.left == null ? right : left));
        else
            maxPath = Math.max(maxPath, Math.max(left + right + root.val, Math.max(left, right)));
        return Math.max(Math.max(left, right) + root.val, root.val);
    }
}